package com.zjsru.leetcode75.level1;

import java.util.*;

/**
 * @Author: cookLee
 * @Date: 2024-01-01
 * 钥匙和房间
 */
public class CanVisitAllRooms {

    /**
     * 主
     * \
     * 输入：rooms = [[1],[2],[3],[]]
     * 输出：true
     * 解释：
     * 我们从 0 号房间开始，拿到钥匙 1。
     * 之后我们去 1 号房间，拿到钥匙 2。
     * 然后我们去 2 号房间，拿到钥匙 3。
     * 最后我们去了 3 号房间。
     * 由于我们能够进入每个房间，我们返回 true。
     * \
     * 输入：rooms = [[1,3],[3,0,1],[2],[0]]
     * 输出：false
     * 解释：我们不能进入 2 号房间。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CanVisitAllRooms canVisitAllRooms = new CanVisitAllRooms();
        List<List<Integer>> rooms = new ArrayList<>();
        rooms.add(Collections.singletonList(1));
        rooms.add(Collections.singletonList(2));
        rooms.add(Collections.singletonList(3));
        rooms.add(Collections.emptyList());
        System.out.println(canVisitAllRooms.canVisitAllRooms(rooms));
    }

    /**
     * 可以访问所有房间
     * 广度优先搜索bfs
     *
     * @param rooms 客房
     * @return boolean
     */
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int len = rooms.size();
        int nodeNum = 0;
        Queue<Integer> queue = new LinkedList<>();
        //初始第一个节点为true，因为第一个节点一定走过
        boolean[] booleans = new boolean[len];
        booleans[0] = true;
        //放入第一个节点下标
        queue.offer(0);
        while (!queue.isEmpty()) {
            nodeNum++;
            //按照下标获取钥匙
            Integer poll = queue.poll();
            List<Integer> room = rooms.get(poll);
            //统计对应的节点是否被访问
            for (Integer key : room) {
                if (!booleans[key]) {
                    booleans[key] = true;
                    queue.offer(key);
                }
            }
        }
        return len == nodeNum;
    }

    boolean[] booleans;
    int num;

    /**
     * 可以访问所有房间
     * 深度优先搜索dfs
     *
     * @param rooms 客房
     * @return boolean
     */
    public boolean canVisitAllRooms2(List<List<Integer>> rooms) {
        int len = rooms.size();
        num = 0;
        booleans  = new boolean[len];
        this.dfs(rooms,0);
        return len == num;
    }

    /**
     * 深度优先搜索助手类
     *
     * @param rooms 客房
     * @param i     我
     */
    private void dfs(List<List<Integer>> rooms, int i) {
        booleans[i] = true;
        num++;
        List<Integer> room = rooms.get(i);
        for (Integer key : room) {
            if (!booleans[key]) {
                this.dfs(rooms, key);
            }
        }
    }

}
